package com.markus.code.二叉树.leetcode;

/**
 * Author:markusZhang
 * Date:Create in 2020/8/11 23:42
 * todo: 二叉树展开为链表
 */
public class LeetCode_114 {
    public static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val){
            this.val = val;
        }
    }
    public void morris(TreeNode root){
        if (root == null){
            return ;
        }
        TreeNode curr = root;
        while(curr != null){
            TreeNode mostRight = curr.left;
            if (mostRight != null){
                while(mostRight.right != null && mostRight.right != curr){
                    mostRight = mostRight.right;
                }
                if (mostRight.right == null){
                    mostRight.right = curr;
                    curr = curr.left;
                    continue;
                }else{
                    //在第二次来到该节点的时候，调整指针。
                    mostRight.right = null;
                    TreeNode right = curr.right;
                    curr.right = curr.left;
                    curr.left = null;
                    while(curr.right != null){
                        curr = curr.right;
                    }
                    curr.right = right;
                }
            }
            curr = curr.right;
        }
    }
    private void printList(TreeNode root){
        while(root != null){
            System.out.print(root.val + " ");
            root = root.right;
        }
    }
    public static void main(String[] args) {
        TreeNode A = new TreeNode(1);
        A.left = new TreeNode(2);
        A.right = new TreeNode(3);
        A.left.left = new TreeNode(4);
        A.left.right = new TreeNode(5);
        A.right.left = new TreeNode(6);
        A.right.right = new TreeNode(7);
        LeetCode_114 demo = new LeetCode_114();
        demo.morris(A);
        demo.printList(A);
    }
}
